﻿using System;
using System.Collections.Generic;
using System.Text;

namespace LeetcodeTest._100._40
{
    /*
     https://leetcode.com/problems/combination-sum/

        39. Combination Sum

         Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

    All numbers (including target) will be positive integers.
    The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

[
  [7],
  [2, 2, 3]
]

         */
    public class Leetcode39
    {
        public IList<IList<int>> CombinationSum(int[] candidates, int target)
        {
            List<List<int>> listRet = new List<List<int>>();
            List<int> listInt = new List<int>();
            int tempValue = 0;
            Array.Sort(candidates);
            for (int i = 0; i < candidates.Length; i++)
            {
                if (candidates[i] > target)
                    break;
                if (candidates[i] == target)
                {
                    listInt = new List<int>();
                    listInt.Add(i);
                    listRet.Add(listInt);
                    break;
                }

                tempValue += candidates[i];
                if (tempValue < target)
                {
                    i--;
                }
            }

            return (IList<IList<int>>)listRet;
        }
    }
}
